/*
*https://leetcode.cn/problems/fruit-into-baskets/description/
*904. 水果成篮
* medium, 彭珵 2024.9.4
* 滑动窗口
*/

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int left = 0; // 左指针，表示当前窗口的起始位置
        int right = 0; // 右指针，表示当前窗口的结束位置
        int ans = 0; // 记录最大水果数量

        // 初始化篮子一号和二号的水果类型
        int ln = fruits[left], rn = fruits[right]; 

        // 遍历整个水果数组
        while (right < fruits.size()) {
            // 如果当前水果属于篮子一号或二号
            if (fruits[right] == rn || fruits[right] == ln) {
                // 更新结果，每次取一个水果就更新一下
                ans = max(ans, right + 1 - left);  
                right++; // 移动右指针，扩展窗口
            } else { // 如果遇到第三种水果
                // 将左指针移动到右指针前一步，左指针指向的水果类型必然不同于右指针
                left = right - 1;  // 移动左指针到 right - 1
                ln = fruits[left]; // 更新第一个篮子的水果类型

                // 移动左指针，直到找到不同的水果类型
                while (left >= 1 && fruits[left - 1] == ln) {
                    left--; // 向左移动左指针
                }

                rn = fruits[right]; // 更新第二个篮子的水果类型
                // 更新最大水果数量
                ans = max(ans, right + 1 - left); // 计算当前窗口的大小
            }
        }
        return ans; // 返回可以收集的最大水果数量
    }
};